//给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。 
//
// 
//
// 在杨辉三角中，每个数是它左上方和右上方的数的和。 
//
// 示例: 
//
// 输入: 5
//输出:
//[
//     [1],     0
//    [1,1],    1
//   [1,2,1],   3
//  [1,3,3,1],  6
// [1,4,6,4,1]  10
//] 
// Related Topics 数组

/**
 * 第四行的3这个数，处于7这个下标
 * 左上角，处于3，右上角，处于3 + 1= 4
 * 7/2 = 3
 * 4/2 = 2
 *
 * x + x + 1 = n + 2
 */
package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class PascalsTriangle {
    public static void main(String[] args) {
        Solution solution = new PascalsTriangle().new Solution();
        List<List<Integer>> lists = solution.generate(0);
        System.out.println(lists);
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> generate(int numRows) {
        if (numRows == 0) {
            return new ArrayList<>();
        }

        ArrayList<List<Integer>> lists = new ArrayList<>();
        if (numRows == 1) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(1);
            lists.add(list);
            return lists;
        }

        // 添加第一行
        ArrayList<Integer> row1 = new ArrayList<>();
        row1.add(1);
        lists.add(row1);

        ArrayList<Integer> row2 = new ArrayList<>();
        row2.add(1);
        row2.add(1);
        lists.add(row2);

        for (int i = 2; i < numRows; i++) {
            int lengthOfRow = i + 1;
            List<Integer> row = new ArrayList<>(lengthOfRow);
            for (int j = 0; j < lengthOfRow; j++) {
                row.add(0);
            }
            // 填充每一行的数据
            row.set(0,1);
            row.set(lengthOfRow - 1,1);
            for (int j = 1; j < lengthOfRow - 1; j++) {
                // 获取上一行，对应的(下标-1，下标)的数据
                List<Integer> lastRow = lists.get(i-1);
                int sum = lastRow.get(j - 1) + lastRow.get(j);
                row.set(j,sum);
            }

            lists.add(row);
        }

        return lists;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}